Disjoint Sparse Table
Given a sequence of static values of length N, a data structure where the preprocessing O(NlogN) allows operations on the upper interval of the sequence to be computed in O(1)
Conditions required for operation
Unit and inverse yuan are not required.
There is no need to use this for operations with inverse roots, such as addition.
Because we can do the same thing with construction O(N) using cumulative sum. The Disjoint Sparse Table allows the user to compute the product of arbitrary intervals by combining a large number of cumulative products.
---
This page is auto-translated from /nishio/Disjoint Sparse Table. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.